Delphi Magazine Collection 2001/Delphi Magazine Collection 20001 (2001).iso/DISKS/Issue28/hash/HASH.ZIP/hash.pas

Pascal/Delphi Source File | 1997-09-29 | 6.6 KB | 293 lines

//----------------------------------------------------------------------------
// File:          hash.pas
// Typ:           Delphi - Unit
// Author:        Peter Welkenbach
// Date:          28.09.97
// Last update:   28.09.97
// Compiler:      Delphi 3.0
// Remarks:       Implementation of a hashtable using external chaining
//
//          uses the hash function used in ELF object files
//
//                c-source of hash-function (Attention: it's wrong there!!)
//                was published in the Book:
//
//                A. Binstock, J. Rex (1995):
//                Practical Algorithms for Programmers,
//                Addison-Wesley
//
// Todo:          1.) check for existing objects with identical data
//                2.) make hashtable persistent
//----------------------------------------------------------------------------
unit Hash;

interface

uses sysutils, classes;

type
  THashObj = class(TObject)
               private
                 HashValue: integer;
               public
                 Name: string;
                 Data: Pointer;
              end;


  THashSlot = class(TObject)
              private
                SlotOfHashValue: integer;
                HashElements: TList;   // of THashObj

              protected
                constructor Create;
                destructor Destroy; override;

                function GetObjByName( Name: pchar ): THashObj;
              end;


  THashTable = class(TList)
                private
                  ClosestPrime: integer;
                  HashElement: THashObj;

                  HashElementList: TList;

                  function ElfHash( name: pchar): integer;

                public
                  HashSlot: THashSlot;

                  constructor Create;
                  destructor Destroy; override;
                  procedure Init(Size: integer);  //
                  procedure AddElementToSlot( Element: String; Data: Pointer);
                  procedure DelElementFromSlot( Element: String );
                  function CountElementsInSlot( SlotOfValues: String): integer;
                  function GetElementFromSlot( Name: String): THashObj;
                  function GetSlot( Slot: string): TList;
              end;




implementation

//--------------------------------------------------
//
//   THashSlot
//
//--------------------------------------------------

constructor THashSlot.Create;
begin
  inherited create;
  HashElements:=Tlist.Create;
end;


destructor THashSlot.Destroy;
var
 i: integer;
 obj: THashObj;
begin
   for i:=0 to HashElements.Count-1 do begin
      obj := HashElements.items[i];
      HashElements.delete(i);
      obj.Free;
   end;
  HashElements.Free;
  inherited destroy;
end;


function THashSlot.GetObjByName( Name: pChar ): THashObj;
var
 i: integer;
 HO: THashObj;

begin
 Result := NIL;
 for i:=0 to HashElements.Count-1 do begin
    HO := HashElements.items[i];
    if (strcomp( pChar(HO.Name), Name) = 0) then begin
         Result:= HO;
         exit;
    end;
 end;
end;



//--------------------------------------------------
//
//  THashTable
//
//--------------------------------------------------
constructor THashTable.Create;
begin
  inherited Create;
  HashElementList:= TList.Create;
end;


destructor THashTable.Destroy;
var
  i: integer;
begin
 for i:=0 to HashElementList.Count-1 do begin
    HashSlot := HashElementList.Items[i];
    HashSlot.Free;
    HashElementList.Delete(i);
 end;
 HashElementList.Free;
 inherited Destroy;
end;



procedure THashTable.Init(Size: integer);
var
 i: integer;
begin

 if Size <= 100 then
    ClosestPrime := 97

 else if (Size >100) and (Size <= 250) then
    ClosestPrime := 241

 else if (Size >250) and (Size <= 400) then
    ClosestPrime := 397

 else if (Size >400) and (Size <= 500) then
    ClosestPrime := 499

 else if (Size >500) and (Size <= 750) then
    ClosestPrime := 743

 else if (Size >750) and (Size <= 1000) then
    ClosestPrime := 997

 else if (Size >1000) and (Size <= 1500) then
    ClosestPrime := 1499

 else if (Size >1500) and (Size <= 2000) then
    ClosestPrime := 1999

 else if (Size >2000) and (Size <= 4000) then
    ClosestPrime := 3989

 else if (Size >4000) and (Size <= 5000) then
    ClosestPrime := 4999


 else if (Size >5000) and (Size <= 7500) then
    ClosestPrime := 7499

 else if (Size >7500) and (Size <= 10000) then
    ClosestPrime := 9973;

 for i:=0 to Size do begin
    HashSlot := THashSlot.Create;
    HashSlot.SlotOfHashValue := i;
    HashElementList.Add( HashSlot);
 end;

end;

procedure THashTable.AddElementToSlot( Element: String; Data: Pointer);
var
  HS: THashSlot;
begin
  HashElement := THashObj.Create;
  HashElement.HashValue := ElfHash( pchar(Trim(Element)) ) mod ClosestPrime;
  HashElement.Name := Element;
  HashElement.Data := Data;

  HS := HashElementList.items[HashElement.HashValue ];

  HS.HashElements.Add( HashElement);
end;


procedure THashTable.DelElementFromSlot( Element: String );
var
  HashValue: integer;
  HS: ThashSlot;
begin
  HashValue := ElfHash(pchar(trim(Element))) mod ClosestPrime;

  HS := HashElementList.items[HashValue ];

  HashElement := HS.GetObjByName( pchar(Element) );
  HashElement.Free;
  HS.HashElements.Remove( HashElement );
  HS.HashElements.Pack;
end;


function THashTable.CountElementsInSlot( SlotOfValues: String): integer;
var
  HashValue: integer;
  HS: ThashSlot;
begin
  HashValue := ElfHash(pchar(trim(SlotOfValues))) mod ClosestPrime;

  HS := HashElementList.items[HashValue ];

  Result := HS.HashElements.count;
end;


function THashTable.GetElementFromSlot( Name: String): THashObj;
var
  HashValue: integer;
  HS: ThashSlot;
begin
  HashValue := ElfHash(pchar(trim(Name))) mod ClosestPrime;

  HS := HashElementList.items[HashValue ];

  Result := HS.GetObjByName( pchar(Name) );
end;


function THashTable.GetSlot( Slot: string): TList;
var
  HS: THashSlot;
  HashValue: integer;
begin
  HashValue := ElfHash(pchar(trim(Slot))) mod ClosestPrime;

  HS := HashElementList.items[ HashValue ];

  Result := HS.HashElements;
end;


function THashTable.ElfHash( name: pchar): integer;
var
 h,g: word;
 i, nCount: integer;

begin
 h:=0;
 nCount := StrLen(name);

 for i:=0 to nCount-1 do begin
    h :=  ( h shl 4 ) + integer(name[i+1]);
    g := h AND $F0000000;
    if ( g <> 0  ) then begin
        h := h xor ( g shr 24 );
        h := h AND (not(g));
     end;
 end;
 Result := h;
end;


end.